On Improving the Balance between the Completion Time and Decoding Delay in Instantly Decodable Network Coded Systems

摘要

This paper studies the complicated interplay of the completion time (as ameasure of throughput) and the decoding delay performance in instantlydecodable network coded (IDNC) systems over wireless broadcast erasure channelswith memory, and proposes two new algorithms that improve the balance betweenthe completion time and decoding delay of broadcasting a block of packets. Wefirst formulate the IDNC packet selection problem that provides joint controlof the completion time and decoding delay as a statistical shortest path (SSP)problem. However, since finding the optimal packet selection policy using theSSP technique is computationally complex, we employ its geometric structure tofind some guidelines and use them to propose two heuristic packet selectionalgorithms that can efficiently improve the balance between the completion timeand decoding delay for broadcast erasure channels with a wide range of memoryconditions. It is shown that each one of the two proposed algorithms issuperior for a specific range of memory conditions. Furthermore, we show thatthe proposed algorithms achieve an improved fairness in terms of the decodingdelay across all receivers.